package solution._0030._0034;

/**
 * Created by chen_snow
 * Date: 2021/5/31 23:28
 * Description: 在排序数组中查找元素的第一个和最后一个位置
 */
public class Solution {

    public static void main(String[] args) {
        searchRange(new int[]{1}, 1);
    }

    public static int[] searchRange(int[] nums, int target) {

        if (nums == null || nums.length == 0){
            return new int[]{-1, -1};
        }

        int index = halfSearch(nums, target, 0, nums.length - 1);
        if (index == -1) {
            return new int[]{-1, -1};
        }

        int left = findEdge(nums, target, index, true);
        int right = findEdge(nums, target, index, false);
        return new int[]{left, right};
    }


    public static int findEdge(int[] nums, int target, int index, boolean isLeft) {
        int result = index;
        int num = index;

        if (isLeft) {
            num = halfSearch(nums, target, 0, index - 1);
            while (num != -1 && result != num) {
                result = num;
                num = halfSearch(nums, target, 0, num - 1);
            }
        } else {
            num = halfSearch(nums, target, index + 1, nums.length - 1);
            while (num != -1 && result != num) {
                result = num;
                num = halfSearch(nums, target, num + 1, nums.length - 1);
            }
        }

        return result;
    }

    public static int halfSearch(int[] nums, int target, int start, int end) {
        if (start > end) {
            return -1;
        }

        int middle = start + (end - start) / 2;

        if (nums[middle] == target) {
            return middle;
        }

        if (nums[middle] > target) {
            return halfSearch(nums, target, start, middle - 1);
        } else {
            return halfSearch(nums, target, middle + 1, end);
        }

    }
}
